package org.nowcoder.leetcode.union;

import java.util.Arrays;

/**
 * Title  : 547. Number of Provinces
 * Source : https://leetcode.cn/problems/number-of-provinces/description/
 * Author : XrazYang
 * Date   : 2024-04-30
 */

public class LeetCode_547 {

    private class UnionFind {
        private int[] parents;

        public UnionFind(int n) {
            parents = new int[n];
            Arrays.fill(parents, -1);
        }

        public int find(int x) {
            if (parents[x] == -1) return x;
            else {
                parents[x] = find(parents[x]);
                return parents[x];
            }
        }

        public void union(int x, int y) {
            int xRoot = find(x);
            int yRoot = find(y);
            if (xRoot != yRoot) {
                parents[xRoot] = yRoot;
            }
        }

        public boolean isConnection(int x, int y) {
            return find(x) == find(y);
        }
    }

    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;
        UnionFind unionFind = new UnionFind(n);

        //遍历所有城市
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (isConnected[i][j] == 1) {
                    unionFind.union(i, j);
                }
            }
        }

        int count = 0;
        for (int i = 0; i < n; i++) {
            if (unionFind.find(i) == i) {
                count++;
            }
        }
        return count;
    }
}
